package array;

public class FirstMissingPositive41 {
    // 注意: 可以在原数组上修改, 见题解, shit
    // 以下已通过, 注意各种continue情况.
    // 该方法的核心在于如何限制交换无休止的进行
    public int firstMissingPositive(int[] nums) {
        // 如果val=nums[i]属于[1, nums.length], 则把 val 放到 nums的val-1这个位置;
        // 否则将nums[i]置为0
        for (int i = 0; i < nums.length; ) {
            int val = nums[i];
            if (val == i+1) {
                // i增加
                i++;
                continue;
            }
            if (val >= 1 && val <= nums.length) {
                int val2 = nums[val-1];
                if (val2 == val) {
                    // 不用交换了, val2已经合法了, i增加, 继续
                    i++;
                } else {
                    nums[val - 1] = val;
                    if (val2 >= 1 && val2 <= nums.length) {
                        // 交换位置, i不变, 继续
                        nums[i] = val2;
                    } else {
                        // 置为0, i增加, 继续
                        nums[i] = 0;
                        i++;
                    }
                }
            } else {
                // 置为0, i增加, 继续
                nums[i] = 0;
                i++;
            }
        }

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != i+1) {
                return i+1;
            }
        }
        return nums.length+1;
    }
}
